<?php 
/**
 * 字符串的排列
 * 输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
 * 思路：
 * Axxxxxxx 分为  A  xxxxxxx 两部分 先闲算xxxx的排列，
 * 然后 A与后面每个字符交换  x Axxxxx , x xAxxxxx,
 * 每个子序列都进行这样的操作
 * 
 */

function Permutation($str)
{
	if (!is_string($str)) {
		return null;
	}
	if (strlen($str) == 0) {
		return null;
	}
	$arrs = [];
	PermutationDetail1($str, 0, $arrs);
	sort($arrs);
	return $arrs;
    
}

function PermutationDetail($str, $k, &$arrs)
{
	if ($k == strlen($str) - 1) {
		array_push($arrs, $str);
	} else {
		for ($i = $k; $i < strlen($str); ++$i) {
			swap($str, $k, $i);
			PermutationDetail($str, $k + 1, $arrs);
			//在最后交换完成入Array之后再交换回来，回到初始状态再进下一个循环
			swap($str, $k, $i);
		}
	}
}



/** 
 * 8皇后问题
 *  8 行8 列
 *  每个数，不能同行同列同对角线
 *  假设 01234567 代表每一行的每一个皇后的列数， （0 代表第0行的第0列）
 *  然后求01234567的全排列
 *  如果 行数相减 ==  列数相减 则是同一对角线上
 *  i - j = str[i] - str[j] 或者 j - i = str[i] - str[j]
 * 01234567 代表
 * @param [type] $str   [description]
 * @param [type] $k     [description]
 * @param [type] &$arrs [description]
 */
function PermutationDetail1($str, $k, &$arrs)
{
	if ($k == strlen($str) - 1) {
		$flat = true;
		for ($a = 0; $a < strlen($str); $a++) {
			for ($b = $a + 1;$b < strlen($str); $b ++) {
				if (($a - $b) == (intval($str[$a]) - intval($str[$b])) || ($b - $a) == (intval($str[$a]) - intval($str[$b]))) {
					$flat = false;
				}
			}
		}
		if ($flat) {
			array_push($arrs, $str);
		}
	} else {
		for ($i = $k; $i < strlen($str); ++$i) {
			swap($str, $k, $i);
			PermutationDetail1($str, $k + 1, $arrs);
			//在最后交换完成入Array之后再交换回来，回到初始状态再进下一个循环
			swap($str, $k, $i);
		}
	}
}


function swap(&$str, $i, $j) {
        $temp = $str[$i];
        $str[$i] = $str[$j];
        $str[$j] = $temp;
}
var_dump(Permutation('01234567'));

